package main

import (
	"fmt"
	. "local/algorithm/util"
	bst "local/datastructure/tree/binarySearchTree"
)

func widthOfBinaryTree(root *TreeNode) int {
	if root == nil {
		return 0
	}
	nq := []*TreeNode{root}
	iq := []int{0}
	size := 1
	maxWidth := 1

	for len(nq) != 0 {
		node := nq[0]
		nq = nq[1:]
		index := iq[0]
		iq = iq[1:]
		size--

		if node.Left != nil {
			nq = append(nq, node.Left)
			iq = append(iq, index*2+1)
		}

		if node.Right != nil {
			nq = append(nq, node.Right)
			iq = append(iq, index*2+2)
		}

		if size == 0 {
			if len(iq) >= 1 {
				maxWidth = max(maxWidth, iq[len(iq)-1]-iq[0]+1)
			}

			size = len(iq)
		}
	}
	return maxWidth
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	t := bst.Generate([]int{10})
	w := widthOfBinaryTree(t)
	fmt.Println(w)
}
